Vés al contingut

Lleis de De Morgan

De la Viquipèdia, l'enciclopèdia lliure
Representació gràfica de les lleis de De Morgan

Les lleis de De Morgan són una part de la lògica proposicional i analítica, i va ser creada per Augustus De Morgan (Madurai, 1806 - Londres, 1871).[1]

Història

[modifica]

Les lleis porten el nom d’Augustus De Morgan (1806–1871),[2] que va introduir una versió formal de les lleis a la lògica proposicional clàssica. La formulació de De Morgan va estar influenciada per l’algebraització de la lògica empresa per George Boole, que posteriorment va consolidar la pretensió de De Morgan a la troballa. Tot i això, Aristòtil va fer una observació similar, que era coneguda pels lògics grecs i medievals. Per exemple, al segle XIV, Guillem d'Ockham va escriure les paraules que resultarien llegint les lleis.[3] Jean Buridan, a la seva Summulae de Dialectica, també descriu les regles de conversió que segueixen les línies de les lleis de De Morgan.[4] Tot i així, a De Morgan se li dona el mèrit d’enunciar les lleis en els termes de la lògica formal moderna i d’incorporar-les al llenguatge de la lògica. Les lleis de De Morgan es poden demostrar fàcilment i fins i tot poden semblar trivials.[5] Tanmateix, aquestes lleis són útils per fer inferències vàlides en proves i arguments deductius.

Les lleis de De Morgan

[modifica]

Les lleis de De Morgan declaren que la suma de n variables globalment negades (o invertides) és igual al producte de les n variables negades individualment, i que inversament, el producte de n variables globalment negades és igual a la suma de les n variables negades individualment.[6]

Prova

[modifica]

Cal utilitzar les taules de valors de veritat,[7]

V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V

Demostració formal

[modifica]

si i només si i .

per a qualsevol x:[7]

inclusió:

o

o

Per tant

inclusió:

o

o

Per tant


i per tant Q.E.D.


per es pot utilitzar un mètode similar.

Amb proposicions

[modifica]

La prova utilitza l'associativitat i la distributivitat de les lleis i .[8]

  • Veritat
  • Si veritat per n

Referències

[modifica]
  1. Hurley, Patrick J. A Concise Introduction to Logic. 12th. Cengage Learning, 2015. ISBN 978-1-285-19654-1. 
  2. DeMorgan’s Theorems Arxivat 2008-03-23 a Wayback Machine. at mtsu.edu
  3. William of Ockham, Summa Logicae, part II, sections 32 and 33.
  4. Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5. ISBN 0-300-08425-0
  5. Augustus De Morgan (1806–1871) Arxivat 2010-07-15 a Wayback Machine. by Robert H. Orr
  6. 2000 Solved Problems in Digital Electronics by S. P. Bali
  7. 7,0 7,1 ; Wu, Vincent«De Morgan's Laws».
  8. Boolean Algebra by R. L. Goodstein. ISBN 0-486-45894-6

Vegeu també

[modifica]